package org.sunny.string;

import org.apache.commons.lang3.StringUtils;

/**
 * 暴力匹配字符串
 *
 * @author Sunny
 * @date 2020/8/17
 */
public class BruteForce1 {

    public static void main(String[] args) {
        System.out.println(bruteForce2("Hello World", "or"));
        System.out.println(bruteForce2("Hello World", "H"));
        System.out.println(bruteForce2("Hello World", "d"));
        System.out.println(bruteForce2("Hello World", "ab"));
    }

    /**
     * 暴力匹配1
     *  以字符为单位，从左到右移动模式串，直到匹配成功
     *  pi 的取值范围 [0, plen)
     *  ti 的取值范围 [0, tlen)
     *
     * @param text 文本串
     * @param pattern 模式串
     * @author Sunny
     * @date 2020/8/17
     */
    public static int bruteForce1(String text, String pattern) {
        if (StringUtils.isBlank(text) || StringUtils.isBlank(pattern)) {
            return -1;
        }

        char[] textChars = text.toCharArray();
        char[] patternChars = pattern.toCharArray();

        int tlen = textChars.length;
        int plen = patternChars.length;

        if (tlen < plen) {
            return -1;
        }

        int pi = 0, ti = 0;

        while (pi < plen && ti < tlen) {
            //如果模式串中的pi索引的字符与文本串中ti索引的字符相等
            if (textChars[ti] == patternChars[pi]) {
                //pi与ti索引都增加1, 匹配下一个字符
                pi++;
                ti++;
            } else {
                //如果ti与pi对应字符不匹配, ti向后移动一位, pi归零
//                ti = ti - pi + 1;
                ti -= pi - 1;
                pi = 0;
            }
        }

        return pi == plen ? ti - pi : -1;
    }

    /**
     * 暴力匹配1 优化
     *  bruteForce1 的问题在于如果pattern串尾部已经超过text串的长度, 程序还是会继续匹配, 平白增加很多次匹配
     *
     *
     * @param text 文本串
     * @param pattern 模式串
     * @author Sunny
     * @date 2020/8/17
     */
    public static int bruteForce2(String text, String pattern) {
        if (StringUtils.isBlank(text) || StringUtils.isBlank(pattern)) {
            return -1;
        }

        char[] textChars = text.toCharArray();
        char[] patternChars = pattern.toCharArray();

        int tlen = textChars.length;
        int plen = patternChars.length;

        if (tlen < plen) {
            return -1;
        }

        int pi = 0, ti = 0, tiMax = tlen - plen;

        //优化点: 限定ti可以匹配的最大索引位置 tiMax
        // ti – pi 是指每一轮比较中 text 首个比较字符的位置
        while (pi < plen && ti - pi <= tiMax) {
            //如果模式串中的pi索引的字符与文本串中ti索引的字符相等
            if (textChars[ti] == patternChars[pi]) {
                //pi与ti索引都增加1, 匹配下一个字符
                pi++;
                ti++;
            } else {
                //如果ti与pi对应字符不匹配, ti向后移动一位, pi归零
//                ti = ti - pi + 1;
                ti -= pi - 1;
                pi = 0;
            }
        }

        //如果pi等于 plen,代表模式串中字符都匹配了, 返回匹配索引位置
        return pi == plen ? ti - pi : -1;
    }
}
